Data compression is required in data handling processes, where too much data is present for practical applications using the data. Commonly, compression is used in communication links, where the time to transmit is long, or where bandwidth is limited. Another use for compression is in data storage, where the amount of media space on which the data is stored can be substantially reduced with compression. Yet another application is a digital copier where an intermediate storage is used for collation, reprint or any other digital copier functions. Generally speaking, scanned images, i.e., electronic representations of hard copy documents, are commonly large, and thus are desirable candidates for compression.
ADCT (Adaptive Discrete Cosine Transform, described for example, by W. H. Chen and C. H. Smith, in "Adaptive Coding of Monochrome and Color Images", IEEE Trans. Comm., Vol. COM-25, pp. 1285-1292, November 1977), as the method disseminated by the JPEG committee will be called in this application, is a lossy system which reduces data redundancies based on pixel to pixel correlations. Generally, in images, on a pixel to pixel basis, an image does not change very much. An image therefore has what is known as "natural spatial correlation". In natural scenes, correlation is generalized, but not exact. Noise makes each pixel somewhat different from its neighbors.
Co-pending U.S. patent application Ser. No. 07/956,128, entitled "Decompression of Standard ADCT-Compressed Images" by R. Eschbach, filed Oct. 2, 1992 and assigned to the same assignee as the present invention (published at EP 590922, on Apr. 6, 1994) and U.S. Pat. No. 5,359,676 to Fan, teach variations on an iterative ADCT decompression method that, after filtering, iteratively checks to assure that the filtered and decompressed image is an image that could have been derived from the original image. During each iteration, a check is made, and, if required, an adjustment is made to the ADCT coefficients, if a possible image is not represented. These references suggested that every block of coefficients is operated upon in an identical manner, and therefore subject to at least one iteration by the system described. This approach works well in hardware implementation, because no overhead in terms of time is generated by iteratively processing blocks that do not need to be checked. If the method of these references is implemented in software, a heavy overhead penalty accrues in terms of time, because processing time is directly dependent upon the number of iterations performed in the decompression process. Accordingly, software performance might be improved if the number of iterations could be reduced. Particularly, iterations where improvement in the image are unlikely to occur, are candidates for reduction.
Generally, as shown in FIG. 1, a JPEG ADCT compression and decompression system is illustrated. A more complete discussion may be had by referencing U.S. Pat. No. 5,321,522 to Eschbach, co-pending U.S. patent application Ser. No. 07/956,128, entitled "Decompression of Standard ADCT-Compressed Images" by R. Eschbach, filed Oct. 2, 1992 and assigned to the same assignee as the present invention (published at EP 590922, on Apr. 6, 1994) and U.S. Pat. No. 5,359,676 to Fan, all incorporated herein by reference. Initially provided is tile memory 10 storing an M.times.M tile of the image. From the portion of the image stored in tile memory, the discrete cosine transform (DCT), a frequency space representation of the image is formed at transformer 12. Hardware implementations are available, such as the C-Cube Microsystems CL550A JPEG image compression processor, which operates in either the compression or the decompression mode according to the proposed JPEG standard. As we will see below, the primary focus of the invention is in software processing, although hardware implementations may be improved, as well. A divisor/quantization device 14 is used, from a set of values referred to as a Q-Table, stored in a Q table memory 16, so that a distinct Q table value is divided into the DCT value, returning the integer portion of the value as the quantized DCT value. A Huffman encoder 20 using statistical encoding the quantized DCT values to generate the compressed image that is output for storage, transmission, etc.
ADCT transforms are well known, and hardware exists to perform the transform on image data, e.g., U.S. Pat. No. 5,049,991 to Niihara, U.S. Pat. No. 5,001,559 to Gonzales et al., and U.S. Pat. No. 4,999,705 to Purl. The primary thrust of these particular patents, however, is moving picture images, and not document images.
To decompress the now-compressed image, and with reference to FIG. 1, a series of functions or steps are followed to reverse of the process described. The Huffman encoding is removed at decoder 50. The image signal now represents the quantized DCT coefficients, which are multiplied at signal multiplier 52 by the Q table values in memory 54 in a process inverse to the compression process. At inverse transformer 56, the inverse transform of the discrete cosine transform is derived, and the output image in the spatial domain is stored at image buffer 58.
With reference now to FIG. 2, a general overview of the compression/decompression process is shown. There exists a set of images which are distinct from each other, but which are similar in the respect that each image in the set compresses to the same ADCT representation. Therefore, any decompression process should produce an output image which is within this set. The knowledge of the set of possible images is coded by the Q-Table used. Since the Q-Table represents divisors of the discrete quantized transform coefficients, and as a result of the quantization process fractional portions of each coefficient are discarded, then the set of possible images represents all those images from which the same quantized transform coefficients can be determined about a range of possible coefficient values for each term of the transform.
FIG. 3 illustrates the principle for the process described in U.S. Pat. No. 5,321,522 to Eschbach, co-pending U.S. patent application Ser. No. 07/956,128 entitled "Decompression of Standard ADCT-Compressed Images" by R. Eschbach, filed Oct. 2, 1992 and assigned to the same assignee as the present invention (published at EP 590922, on Apr. 6, 1994) and U.S. Pat. No. 5,359,676 to Fan, and how these references vary from the standard process described in FIG. 1. The original image is compressed; the compressed representation is decompressed. The decompressed image is additionally filtered to improve appearance, but in doing so, it may be forced outside the range of images that are possibly derived from the original image. The DCT representation of the image is therefore altered, in order to force the image into the acceptable range of images. The processes may be used iteratively.
The process described in these references was developed to improve the quality of JPEG compressed images under the assumption that every block was decompressed in an identical manner, which also means that every block was iteratively processed. This is an approach that works well for hardware applications because no overhead is generated by iterating on blocks that need not be operated upon. In software implementations, however, the actual decompression speed is governed by the number of iterations times the number of blocks the iteration is performed on. A critical element of improving the software performance is the prediction of whether a block is a candidate for iterative post-processing or not.
All of the references cited herein above are incorporated by reference for their teachings.